﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _04_Graph
{
   // 并查集 简化版
   class UnionFind
   {
      private Dictionary<Node, List<Node>> setMap;

      public UnionFind(List<Node> nodes)
      {
         setMap = new Dictionary<Node, List<Node>>();
         foreach (var node in nodes)
         {
            List<Node> set = new List<Node>();
            set.Add(node);
            setMap.Add(node, set);
         }
      }

      // 判断from和to是否在同一集合
      public bool IsSameSet(Node from, Node to)
      {
         return setMap[from] == setMap[to];
      }

      // 合并集合
      public void Union(Node from, Node to)
      {
         List<Node> fromset = setMap[from];
         List<Node> toset = setMap[to];

         // to中结点全部加入到from中
         foreach (var node in toset)
         {
            fromset.Add(node);
            // 所有to结点指向fromset
            setMap[node] = fromset;
         }
      }
   }
}
